Paper 2019/549

Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir

Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum

Abstract

The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography. We show that solving the End-of-Metered-Line problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n). Combining our construction with a hash family proposed by Canetti et al. [STOC 2019] gives rise to a distribution in the class CLS, which is provably hard under the assumption that any one of a class of fully homomorphic encryption (FHE) schemes has almost-optimal security against quasi-polynomial time adversaries, and under the additional worst-case assumption that there is no polynomial time algorithm for counting the number of satisfying assignments for formulas over a polylogarithmic number of variables.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. STOC 2019
DOI
10.1145/3313276.3316400
Keywords
TFNPPPADNash EquilibriumFiat-Shamir transformation
Contact author(s)
achoud @ cs jhu edu
hubacek @ iuuk mff cuni cz
ckamath @ ist ac at
pietrzak @ ist ac at
alon rosen @ idc ac il
rothblum @ alum mit edu
History
2019-05-23: received
Short URL
https://ia.cr/2019/549
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/549,
      author = {Arka Rai Choudhuri and Pavel Hubacek and Chethan Kamath and Krzysztof Pietrzak and Alon Rosen and Guy N.  Rothblum},
      title = {Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/549},
      year = {2019},
      doi = {10.1145/3313276.3316400},
      url = {https://eprint.iacr.org/2019/549}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.